home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / bplus20.zip / CPLUS.C < prev    next >
Text File  |  1989-08-04  |  40KB  |  1,045 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 2.0            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                    Copyright (C) 1987-1989 by                    */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7900 Edgewater Drive                        */
  12. /*                      Wilsonville, Oregon  97070                  */
  13. /*                      (503) 694 - 1449                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. #include <sys\types.h>            /*  delete this line for Turbo C  */
  22. #include <sys\stat.h>
  23. #include <string.h>
  24. #include "bplus.h"
  25.  
  26.  
  27. /*  macros, constants, data types  */
  28.  
  29. #define  NULLREC      (-1L)  /* special value for RECPOS variable */
  30. #define  FREE_BLOCK   (-2)   /* designates a free block in index file */
  31.         /* the address of an entry in a block */
  32. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  33.         /* the size of an entry */
  34. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  35.         /* the cache changed indicator */
  36. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  37.         /* the index file handle for memblock j */
  38. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  39.         /* memory cache block j */
  40. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  41.         /* number of times cache blk j is referenced */
  42. #define  BUFCOUNT(j)      (mci->cache[j].count)
  43.         /* address of current block for level j */
  44. #define  CB(j)            (pci->pos[j].cblock)
  45.         /* offset of current block for level j */
  46. #define  CO(j)            (pci->pos[j].coffset)
  47. #define  TRUE             1
  48. #define  FALSE            0
  49.  
  50.  
  51. /*  declare some global variables  */
  52.  
  53. IX_DESC      *pci;                       /* pointer to index descriptor   */
  54. IX_BUFFER    bt_buffer;                  /* memory cache for index blocks */
  55. IX_BUFFER    *mci = &bt_buffer;          /* pointer to cache index blocks */
  56. BLOCK        *block_ptr;                 /* pointer to index record block */
  57. BLOCK        *spare_block;               /* pointer to spare index block  */
  58. int          cache_ptr = 0;              /* index to cache memory pool    */
  59. int          cache_init = 0;             /* 1 when cache is initilized    */
  60. int          split_size = IXB_SPACE;     /* split block when greater than */
  61. int          comb_size  = (IXB_SPACE/2); /* combine blocks when less than */
  62.  
  63. /* #define memmove     memcpy */    /* Use this macro for MicroSoft C 4.0 */
  64.  
  65. /* list all function prototypes */
  66. void pascal error(int, long);
  67. void pascal read_if(long, char *, int);
  68. void pascal write_if(int, long, char *, int);
  69. int  pascal creat_if(char *);
  70. int  pascal open_if(char *);
  71. void pascal reset_buffers(IX_DESC *);
  72. void pascal close_if(int);
  73. void pascal update_block(void);
  74. void pascal init_cache(void);
  75. int  pascal find_cache(RECPOS);
  76. int  pascal new_cache(void);
  77. void pascal load_cache(RECPOS);
  78. void pascal get_cache(RECPOS);
  79. void pascal retrieve_block(int, RECPOS);
  80. int  pascal prev_entry(int);
  81. int  pascal next_entry(int);
  82. void pascal copy_entry(ENTRY *, ENTRY *);
  83. int  pascal scan_blk(int);
  84. int  pascal last_entry(void);
  85. void pascal write_free( RECPOS, BLOCK *);
  86. RECPOS pascal get_free(void);
  87. int  pascal find_block(ENTRY *, int *, int *);
  88. void pascal movedown(BLOCK *, int, int);
  89. void pascal moveup(BLOCK *, int, int);
  90. void pascal ins_block(BLOCK *, ENTRY *, int);
  91. void pascal del_block(BLOCK *, int);
  92. void pascal split(int, ENTRY *, ENTRY *);
  93. void pascal ins_level(int, ENTRY *);
  94. int  pascal insert_ix(ENTRY *, IX_DESC *);
  95. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  96. int  pascal combineblk(RECPOS, int);
  97. void pascal replace_entry(ENTRY *);
  98. void print_blk(BLOCK *);
  99.  
  100.  
  101. /*  file I/O for B-PLUS module  */
  102.  
  103. void pascal error(j, l)               /* print file error messages */
  104.   int j;                              /* error number */
  105.   long l;                             /* current file position */
  106.   {
  107.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  108.                            "ERROR WHILE READING FILE",
  109.                            "ERROR WHILE WRITING FILE"};
  110.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  111.     exit(1);                  /* delete this line to not halt program */
  112.                               /* and call your error handlng routine */
  113.   } /* error */
  114.  
  115.  
  116. void pascal read_if(start, buf, nwrt)    /* read pci index file */
  117.   long start;                            /* file read position */
  118.   char *buf;                             /* data holding buffer */
  119.   int nwrt;                              /* number bytes to read */
  120.   {
  121.     long err;
  122.           /* seek to read position in current index file */
  123.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  124.          /* if no error read an index file block */
  125.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  126.          /* call error routine if number bytes read != nwrt */
  127.     if (err != 0) error(1, start);
  128.   } /* read_if */
  129.  
  130.  
  131. void pascal write_if(handle, start, buf, nwrt)   /* write index record */
  132.   int handle;                        /* write to this file handle */
  133.   long start;                        /* write to this position in file */
  134.   char *buf;                         /* write data from this buffer */
  135.   int nwrt;                          /* write this many bytes of data */
  136.   {
  137.     long err;
  138.          /* seek to file write position */
  139.     err = start - lseek(handle, start, SEEK_SET);
  140.          /* if no error write index block block */
  141.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  142.          /* call error routine if number bytes written != nwrt */
  143.     if (err != 0) error(2, start);
  144.   } /* write_if */
  145.  
  146.  
  147. int pascal creat_if(fn)               /* make a new index file */
  148.   char *fn;                           /* name and path of file */
  149.   {
  150.     int   ret;
  151.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  152.     if (ret  < 0) error(0,0L);        /* there was an error if ret < 0 */
  153.     return (ret);
  154.   } /* creat_if */
  155.  
  156.  
  157. int pascal open_if(fn)                /* open an existing index file */
  158.   char *fn;                           /* path and name of index file */
  159.   {
  160.     int  ret;
  161.     ret = open(fn,O_RDWR|O_BINARY);
  162.     if (ret < 1) error(0,0L);         /* there was an error is ret < 1 */
  163.     return (ret);
  164.   } /* open_if */
  165.  
  166.  
  167. void pascal close_if(handle)          /* close an open index file */
  168.   int handle;                         /* with this file handle    */
  169.   {
  170.     if(close(handle) < 0)  error(2,0L);
  171.   } /*  close_if */
  172.  
  173.  
  174. int cdecl open_index(name, pix, dup)  /* open and initilize index file */
  175.   char *name;                         /* path and name of index file */
  176.   IX_DESC *pix;                       /* pointer to index descriptor */
  177.   int dup;                            /* allow duplicate keys if != 0 */
  178.   {
  179.     pci = pix;                        /* pci is global index descriptor */
  180.     pci->ixfile = open_if(name);      /* file handle */
  181.     pci->duplicate = dup;             /* set duplicate keys flag */
  182.     pci->root_dirty = FALSE;
  183.      /* read root descriptor for index */
  184.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  185.     if (!cache_init)                   /* if cache not initilized */
  186.       {
  187.         init_cache();                  /* initilize cache memory */
  188.         cache_init = 1;                /* but only once */
  189.       }
  190.     first_key(pix);                    /* position to first index key */
  191.     return ( IX_OK );
  192.   } /* open_index */
  193.  
  194.  
  195. void cdecl buffer_flush(pix)         /* flushes internal index buffers */
  196.   IX_DESC *pix;
  197. {
  198.   int i;
  199.   if (pix->root_dirty)
  200.   {
  201.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  202.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  203.     pix->root_dirty = FALSE;
  204.   }
  205.   for (i = 0; i < NUM_BUFS; i++)
  206.   {
  207.     if ( (BUFHANDLE(i) == pix->ixfile) && BUFDIRTY(i) )
  208.     {
  209.       write_if(BUFHANDLE(i),
  210.            BUFBLOCK(i).brec,
  211.            (char *) &BUFBLOCK(i),
  212.            sizeof(BLOCK));
  213.       BUFDIRTY(i) = FALSE;
  214.     }
  215.   }
  216. }
  217.  
  218. void pascal reset_buffers(pix)
  219.   IX_DESC *pix;
  220.   {
  221.     int i;
  222.     for (i = 0; i < NUM_BUFS; i++)
  223.       if (BUFHANDLE(i) == pix->ixfile) BUFBLOCK(i).brec = NULLREC;
  224.   }
  225.  
  226.  
  227. int cdecl close_index(pix)           /* close index file */
  228.   IX_DESC *pix;
  229.   {
  230.     int ret = IX_OK;
  231.     buffer_flush(pix);
  232.       reset_buffers(pix);
  233.     close_if(pix->ixfile);
  234.     return( ret );
  235.   } /* close_index */
  236.  
  237.  
  238.  
  239. int cdecl make_index(name, pix, dup)       /* create a new index file */
  240.   char *name;                        /* pointer to path and file name */
  241.   IX_DESC *pix;                      /* pointer to index descriptor */
  242.   int dup;                           /* duplicate keys allow is != 0 */
  243.   {
  244.     pci = pix;             /* set global pci to this index descriptor */
  245.     pci->ixfile = creat_if(name);
  246.     pci->root_dirty = FALSE;
  247.     pci->duplicate = dup;
  248.     pci->dx.nl = 1;               /* the only block is the root */
  249.     pci->dx.ff = NULLREC;         /* there are no free index blocks */
  250.     pci->level = 0;               /* the root is level 0 */
  251.     CO(0) = -1;                   /* the current block offset is -1 */
  252.     CB(0) = 0L;                   /* the current block address 0L */
  253.     pci->root.brec = 0L;          /* root block address is 0L */
  254.     pci->root.bend = 0;           /* no entries yet so block end is 0 */
  255.     pci->root.p0 = NULLREC;       /* p0 points to next index level */
  256.  
  257.          /* write the root block of the index descriptor */
  258.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  259.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  260.     if (!cache_init)
  261.       {                        /* initiate memory cache but only once */
  262.         init_cache();
  263.         cache_init = 1;
  264.       }
  265.     first_key(pix);            /* initialize to first key in index */
  266.     return ( IX_OK );
  267.   } /* make_index */
  268.  
  269.  
  270. /*  cache I/O for BPLUS  */
  271.  
  272.  
  273. void pascal update_block()
  274.   {
  275.    /* set flag that a memory block has changed     */
  276.     if (block_ptr == &(pci->root)) pci->root_dirty = TRUE;
  277.     else  BUFDIRTY(cache_ptr) = TRUE;
  278.   } /* update_block */
  279.  
  280.  
  281. void pascal init_cache()       /* initialize the cache memory buffers */
  282.   {
  283.     register int  j;
  284.     for (j = 0; j < NUM_BUFS; j++)
  285.       {  BUFDIRTY(j) = 0;          /* the buffer has not been changed */
  286.          BUFCOUNT(j) = 0;                /* number of references is 0 */
  287.          BUFBLOCK(j).brec = NULLREC;    /* each memory block is empty */
  288.       }
  289.   } /* init_cache */
  290.  
  291.  
  292. int pascal find_cache(r)          /* find a block in the cache memory */
  293.   RECPOS r;
  294.   {
  295.     register int  j;
  296.     for (j = 0; j < NUM_BUFS; j++)    /* repeat for each index buffer */
  297.       {
  298.              /* check handle and index address for a match */
  299.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  300.          {  cache_ptr = j;            /* if match, set cache_ptr */
  301.             return (1);               /* and return true */
  302.       }  }
  303.     return (-1);               /* return false if not in cache memory */
  304.   } /* find_cache */
  305.  
  306.  
  307. int pascal new_cache()             /* assign a block in cache memory */
  308.   {
  309.     register int  i;
  310.     i = (cache_ptr + 1) % NUM_BUFS;    /* assign memory buffer */
  311.          /* if it has been changed, save it to disk */
  312.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  313.                               BUFBLOCK(i).brec,
  314.                               (char *) &BUFBLOCK(i),
  315.                               sizeof(BLOCK));
  316.     BUFHANDLE(i) = pci->ixfile;        /* save index file handle */
  317.     BUFDIRTY(i) = 0;                   /* buffer change flag is false */
  318.     return (i);                        /* return memory buffer pointer */
  319.   } /* new_cache */
  320.  
  321.  
  322. void pascal load_cache(r)         /* load index block in cache memory */
  323.   RECPOS r;
  324.   {
  325.     cache_ptr = new_cache();        /* get a block in cache memory */
  326.                                     /* and then load the index block */
  327.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  328.   } /* load_cache */
  329.  
  330.  
  331. void pascal get_cache(r)            /* load an index block into cache */
  332.   RECPOS r;
  333.   {
  334.     if (find_cache(r) < 0)         /* if block is not in cache memory */
  335.        load_cache(r);              /* load the block in memory */
  336.                                    /* and set block point to this block */
  337.     block_ptr = &BUFBLOCK(cache_ptr);
  338.   } /* get_cache */
  339.  
  340.  
  341. void pascal retrieve_block(j, r)    /* load an index block */
  342.   int j;
  343.   RECPOS r;
  344.   {
  345.     if (j == 0)                     /* if the block wanted is the root */
  346.        block_ptr = &(pci->root);    /* then point to the root */
  347.     else  get_cache(r);             /* else get from cache memory */
  348.     CB(j) = block_ptr->brec;        /* store index block address */
  349.   } /* retrieve_block */
  350.  
  351.  
  352. /*  low level functions of BPLUS  */
  353.  
  354. int pascal prev_entry(off)        /* back up one entry in current block */
  355.   int off;
  356.   {
  357.      if (off <= 0)                /* if off <= can not back up */
  358.        {
  359.          off = -1;                /* set to beginning of block */
  360.          CO(pci->level) = off;
  361.        }
  362.      else
  363.        off = scan_blk(off);       /* find previous entry */
  364.      return(off);
  365.   } /* prev_entry */
  366.  
  367.  
  368. int pascal next_entry(off)        /* find next entry in current block */
  369.   int off;
  370.   {
  371.      if (off == -1)               /* at beginning of the block */
  372.        off = 0;
  373.      else                         /* move to next entry if not at end */
  374.        {
  375.          if (off < block_ptr->bend)
  376.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  377.        }
  378.      CO(pci->level) = off;       /* save the offset position in block */
  379.      return (off);
  380.   } /* next_entry */
  381.  
  382.  
  383. void pascal copy_entry(to, from)  /* copy an entry */
  384.   ENTRY *to;                     /* to here */
  385.   ENTRY *from;                   /* from here */
  386.   {
  387.     int me;
  388.     me = ENT_SIZE(from);         /* get the entry's size */
  389.     memmove(to, from, me);        /* and copy */
  390.   } /* copy_entry */
  391.  
  392.  
  393. int pascal scan_blk(n)           /* find the offset of last entry in */
  394. int n;                           /* current block before postion n */
  395.   {
  396.      register int off, last;
  397.      off = 0;
  398.      last = -1;
  399.      while (off < n )            /* repeat until position >= n */
  400.        {  last = off;
  401.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  402.        }
  403.      CO(pci->level) = last;      /* save new block offset positioon */
  404.      return (last);
  405.   } /* scan_blk */
  406.  
  407.  
  408. int pascal last_entry()          /* find offset of last entry in block */
  409.   {
  410.      return( scan_blk(block_ptr->bend) );
  411.   } /* last_entry */
  412.  
  413.  
  414. /*  maintain list of free index blocks  */
  415.  
  416. void pascal write_free(r, pb)    /* update list of free index blocks */
  417.   RECPOS r;                      /* free index position */
  418.   BLOCK *pb;                     /* free block */
  419.   {
  420.     pb->p0 = FREE_BLOCK;         /* mark as free */
  421.     pb->brec = pci->dx.ff;       /* keep old first free address */
  422.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  423.     pci->dx.ff = r;              /* set first free address to r */
  424.   } /* write_free */
  425.  
  426.  
  427. RECPOS pascal get_free()         /* get address of free index block */
  428.   {
  429.     RECPOS  r, rt;
  430.  
  431.     r = pci->dx.ff;              /* use block address ff if free */
  432.     if ( r != NULLREC )
  433.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  434.          pci->dx.ff = rt;        /* save next free index block */
  435.       }
  436.     else                         /* else add to end of index file */
  437.       r = filelength (pci->ixfile);
  438.     return (r);                  /* return index block address */
  439.   } /* get_free */
  440.  
  441.  
  442. /*  general BPLUS block level functions  */
  443.  
  444.  
  445. int pascal find_block(pe, off, poff)
  446.   ENTRY *pe;
  447.   int *off;
  448.   int *poff;
  449.   {
  450.     register int pos, nextpos, ret;
  451.     pos = -1;
  452.     nextpos = 0;
  453.     ret = 1;
  454.     while ( nextpos < block_ptr->bend)
  455.       {
  456.         ret = strcmp((char *)(pe->key),
  457.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  458.     if (ret <= 0) break;
  459.         pos = nextpos;
  460.     nextpos += ENT_SIZE(ENT_ADR(block_ptr,pos));
  461.     /* nextpos = next_entry(pos); */
  462.       }
  463.     *poff = pos;
  464.     if (ret == 0) *off = nextpos;
  465.     else *off = pos;
  466.     CO(pci->level) = *off;
  467.     return (ret);
  468.   } /* find_block */
  469.  
  470.  
  471. void pascal movedown(pb, off, n)       /* move part of block downward */
  472.   BLOCK *pb;                           /* block to move down */
  473.   int off;                             /* start move here */
  474.   int n;                               /* move this far */
  475.   {
  476.     memmove(ENT_ADR(pb, off),
  477.            ENT_ADR(pb, off + n),
  478.            pb -> bend - (off + n));
  479.   } /* movedown */
  480.  
  481.  
  482. void pascal moveup(pb, off, n)        /* move part of a block upward */
  483.   BLOCK *pb;                          /* the block */
  484.   int off;                            /* start move here */
  485.   int n;                              /* move up n bytes */
  486.   {
  487.     memmove(ENT_ADR(pb, off + n),
  488.             ENT_ADR(pb, off),
  489.             pb->bend - off);
  490.   } /* moveup */
  491.  
  492.  
  493. void pascal ins_block(pb, pe, off)      /* insert entry into a block */
  494.   BLOCK *pb;                            /* add to this block */
  495.   ENTRY *pe;                            /* add this entry */
  496.   int off;                              /* at this position */
  497.   {
  498.     int size;
  499.     size = ENT_SIZE(pe);                /* size of new entry */
  500.     moveup(pb,off,size);                /* move entries to make room */
  501.     copy_entry(ENT_ADR(pb,off),pe);     /* copy new entry */
  502.     pb->bend += size;                   /* adjust block size */
  503.   } /* ins_block */
  504.  
  505.  
  506. void pascal del_block(pb, off)          /* delete entry in a block */
  507.   BLOCK *pb;                            /* this block */
  508.   int off;                              /* delete entry at this position */
  509.   {
  510.     int ne;
  511.     ne = ENT_SIZE(ENT_ADR(pb, off));   /* size of deleted entry */
  512.     movedown(pb, off, ne);             /* move entries down */
  513.     pb->bend -= ne;                    /* adjust block size */
  514.   } /* del_block */
  515.  
  516.  
  517. /*  position at start/end of index  */
  518.  
  519. int cdecl first_key(pix)              /* position to first key */
  520.   IX_DESC *pix;                       /* in this index file */
  521.   {
  522.     pci = pix;                        /* set global index descriptor */
  523.     block_ptr = &(pci->root);         /* start with the root */
  524.     CB(0) = 0L;                       /* root address is 0L */
  525.     CO(0) = -1;                       /* offset is -1 */
  526.     pci->level = 0;                   /* 0 level in index file */
  527.     while(block_ptr->p0 != NULLREC)   /* repeat for all levels */
  528.       {                               /* get index block for next level */
  529.         retrieve_block(++(pci->level), block_ptr->p0);
  530.         CO(pci->level) = -1;          /* position to start of block */
  531.       }
  532.     return ( IX_OK );
  533.   } /* first_key */
  534.  
  535.  
  536. int cdecl last_key(pix)               /* position at last key */
  537.   IX_DESC *pix;                       /* in this index file */
  538.   {
  539.     long  ads;
  540.     pci = pix;
  541.     block_ptr = &(pci->root);         /* start with the root */
  542.     CB(0) = 0L;
  543.     pci->level = 0;
  544.     if(last_entry() >= 0)             /* repeat for all levels */
  545.       {                               /* get block for next level */
  546.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  547.              retrieve_block(++(pci->level), ads);
  548.       }
  549.     CO(pci->level) = block_ptr->bend; /* set offset position to the end */
  550.     return ( IX_OK );
  551.   } /* last_key */
  552.  
  553.  
  554. /*  get next, previous entries  */
  555.  
  556. int cdecl next_key(pe, pix)           /* get next key */
  557.   ENTRY *pe;                          /* and put it here */
  558.   IX_DESC *pix;                       /* for this index */
  559.   {
  560.     RECPOS  address;
  561.     pci = pix;
  562.                                       /* get block for current level */
  563.     retrieve_block(pci->level, CB(pci->level));
  564.                                       /* set address for next level */
  565.     if(CO(pci->level) == -1) address = block_ptr->p0;
  566.     else
  567.       {
  568.         if (CO(pci->level) == block_ptr->bend) address = NULLREC;
  569.         else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  570.       }
  571.     while (address != NULLREC)        /* repeat until at leaf level */
  572.       {
  573.          retrieve_block(++(pci->level), address);
  574.          CO(pci->level) = -1;
  575.          address = block_ptr->p0;
  576.       }
  577.     next_entry(CO(pci->level));       /* get next entry for leaf block */
  578.     if (CO(pci->level) == block_ptr->bend)   /* check for end of block */
  579.       {
  580.         do
  581.           { if(pci->level == 0)       /* if this is the root block */
  582.               {
  583.                 last_key(pci);        /* go to end of root block */
  584.                 return (EOIX);        /* return end of index file */
  585.               }
  586.             --(pci->level);           /* level of ancestor block */
  587.             retrieve_block(pci->level, CB(pci->level));
  588.             next_entry(CO(pci->level));  /* next entry for ancestor */
  589.           } while (CO(pci->level) == block_ptr->bend);
  590.       }
  591.                                       /* copy the next entry and return */
  592.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  593.     return ( IX_OK );
  594.   } /* next_key */
  595.  
  596.  
  597. int cdecl prev_key(pe, pix)          /* get the previous key */
  598.   ENTRY *pe;                         /* put it here */
  599.   IX_DESC *pix;                      /* for this index */
  600.   {
  601.     RECPOS  address;
  602.     pci = pix;
  603.                                      /* get block for current level */
  604.     retrieve_block(pci->level, CB(pci->level));
  605.     prev_entry(CO(pci->level));      /* previous entry in this block */
  606.     if (CO(pci->level) == -1)
  607.       address = block_ptr->p0;
  608.     else
  609.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  610.     if (address != NULLREC)          /* go to the leaf level of index */
  611.       { do
  612.           {
  613.             retrieve_block(++(pci->level), address);
  614.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  615.           } while (address != NULLREC);
  616.       }
  617.     if (CO(pci->level) == -1)        /* check if at beginning of block */
  618.       { do
  619.           {
  620.             if(pci->level == 0)      /* if this is the root block */
  621.               {
  622.                 first_key(pci);      /* get first key */
  623.                 return (EOIX);       /* and return end of index */
  624.               }
  625.             --(pci->level);          /* level for ancestor block */
  626.           } while (CO(pci->level) == -1);   /* repeat if beginning */
  627.         retrieve_block(pci->level, CB(pci->level));   /* get block  */
  628.       }
  629.                                      /* copy entry and return */
  630.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  631.     return ( IX_OK );
  632.   } /* prev_key */
  633.  
  634.  
  635. /*  insert new entries into tree  */
  636.  
  637. void pascal split(l, pe, e)           /* split an index block */
  638.   int l;                              /* level in tree */
  639.   ENTRY *pe;                          /* entry to insert */
  640.   ENTRY *e;                           /* entry to pass up to next level */
  641.   {
  642.     int  half, ins_pos, size;
  643.     ins_pos = CO(pci->level);         /* save current offset */
  644.                                       /* and divide block in half */
  645.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  646.     if (half == ins_pos)              /* if inserting at half */
  647.       *e = *pe;                       /* pass up entry pe */
  648.     else                              /* else copy entry at half */
  649.       {
  650.          copy_entry(e, ENT_ADR(block_ptr, half));
  651.          size = ENT_SIZE(e);
  652.          movedown(block_ptr, half, size);   /* move block entries down */
  653.          block_ptr->bend -= size;           /* and adjust the size */
  654.       }
  655.     spare_block = &BUFBLOCK(new_cache());   /* allocate a spare block */
  656.     memmove(spare_block->entries,           /* and copy half the entries */
  657.            ENT_ADR(block_ptr,half),
  658.            block_ptr->bend - half);
  659.     spare_block->brec = get_free();         /* index address of new block */
  660.     spare_block->bend = block_ptr->bend - half;    /* set size of block */
  661.     spare_block->p0 = e->idxptr;            /* set all the pointers */
  662.     block_ptr->bend = half;
  663.     e->idxptr = spare_block->brec;
  664.     if (ins_pos < half)                     /* insert the new entry */
  665.       ins_block(block_ptr,pe,ins_pos);      /* in current block */
  666.     else if (ins_pos > half)                /* else insert the entry */
  667.       {                                     /* in the spare block */
  668.          ins_pos -= ENT_SIZE(e);
  669.          ins_block(spare_block,pe,ins_pos - half);
  670.          CB(l) = e->idxptr;                 /* set block address */
  671.          CO(l) = CO(l) - half;              /* and offset */
  672.       }
  673.     write_if(pci->ixfile, spare_block->brec,   /* write to disk */
  674.              (char *) spare_block, sizeof(BLOCK));
  675.   } /* split */
  676.  
  677.  
  678. void pascal ins_level(l, e)        /* insert an entry e */
  679.   int l;                           /* into block level l */
  680.   ENTRY *e;
  681.   {
  682.     int  i;
  683.     if ( l < 0)                    /* tree height has increased */
  684.       {  for (i = 1; i < MAX_LEVELS; i++)   /* save offset and addresses */
  685.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  686.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  687.            }
  688.                                    /* copy old root to spare block */
  689.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  690.                                   /* get index address and write to disk */
  691.          spare_block->brec = get_free();
  692.          write_if(pci->ixfile, spare_block->brec,
  693.                   (char *) spare_block, sizeof(BLOCK));
  694.          pci->root.p0 = spare_block->brec;    /* set p0 pointer */
  695.          copy_entry((ENTRY *) (pci->root.entries), e);  /* copy insert e */
  696.          pci->root.bend = ENT_SIZE(e);        /* root contains only e */
  697.          CO(0) = 0;                           /* root offset is 0 */
  698.          pci->level = 0;                      /* set current level */
  699.          (pci->dx.nl)++;                      /* increment no. of levels */
  700.      pci->root_dirty = TRUE;
  701.       }
  702.     else ins_block(block_ptr,e,CO(l));        /* insert in current block */
  703.   } /* ins_level */
  704.  
  705.  
  706. int pascal insert_ix(pe, pix)         /* insert at current level */
  707.   ENTRY *pe;                          /* insert entry pe */
  708.   IX_DESC *pix;                       /* into this index */
  709.   {
  710.     ENTRY    e, ee;
  711.     int h;
  712.     h = 0;
  713.     pci = pix;
  714.     ee = *pe;
  715.     do
  716.       {
  717.          if(CO(pci->level) >= 0)      /* set new offset */
  718.            CO(pci->level) +=
  719.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  720.          else
  721.            CO(pci->level) = 0;
  722.          update_block();           /* we are going to change this block */
  723.                                    /* if new block size < split size */
  724.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  725.            {
  726.              ins_level(pci->level, &ee);   /* insert into current block */
  727.              break;                        /* and break */
  728.            }
  729.          else
  730.            {
  731.              h = 1;                        /* must reset index pointers */
  732.              split(pci->level,&ee, &e);    /* split the current block */
  733.              ee = e;                       /* this entry is passed up */
  734.              pci->level--;                 /* to insert at this level */
  735.              if (pci->level < 0)           /* increase tree height */
  736.                {
  737.                  ins_level(pci->level, &e);
  738.                  break;
  739.                }
  740.                                            /* get block for next level */
  741.              retrieve_block(pci->level, CB(pci->level));
  742.            }
  743.       }
  744.     while (1);
  745.     if (h) find_ix(pe, pix, 0);           /* reset pointers if necessary */
  746.     return ( IX_OK );
  747.   } /* insert_ix */
  748.  
  749.  
  750. /*  BPLUS find and add key functions  */
  751.  
  752. int pascal find_ix(pe, pix, find)     /* search an index file */
  753.   ENTRY *pe;                          /* for this entry */
  754.   IX_DESC *pix;                       /* in this index */
  755.   int find;                           /* 1 to add_key, 0 to find_key */
  756.   {
  757.     int      level, off, poff, ret;
  758.     int      savelevel, saveoff, h;
  759.     RECPOS   ads, saveads;
  760.     pci = pix;
  761.     ads = 0L;
  762.     level = 0;
  763.     h = 0;
  764.     while (ads != NULLREC)
  765.       {  pci->level = level;
  766.          retrieve_block(level, ads);
  767.      if (find_block(pe, &off, &poff) == 0) ret = 1;
  768.      else ret = 0;
  769.      if (ret && find && !pci->duplicate) break;
  770.      if(ret && pci->duplicate)
  771.      {
  772.        saveads = ads;
  773.        savelevel = level;
  774.        saveoff = off;
  775.        off = poff;
  776.        h = 1;
  777.      }
  778.          if (off == -1)
  779.            ads = block_ptr->p0;
  780.          else
  781.        ads = ENT_ADR(block_ptr, off)->idxptr;
  782.          CO(level++) = off;
  783.        }
  784.      if (h && find)
  785.      {
  786.        if (!ret)
  787.        {
  788.      retrieve_block(savelevel, saveads);
  789.      pci->level = savelevel;
  790.      ret = 1;
  791.        }
  792.        CO(savelevel) = saveoff;
  793.      }
  794.      return ( ret );
  795.    } /* find_ix */
  796.  
  797.  
  798. int cdecl find_key(pe, pix)           /* find a key */
  799.   ENTRY *pe;                          /* this entry */
  800.   IX_DESC *pix;                       /* in this index */
  801.   {
  802.     int ret;
  803.     ret = find_ix(pe, pix, 1);       /* find_ix does all the work */
  804.                                      /* if found, copy the entry */
  805.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  806.     return ( ret );
  807.   } /* find_key */
  808.  
  809.  
  810. int cdecl add_key(pe, pix)            /* add a new key */
  811.   ENTRY *pe;                          /* this entry */
  812.   IX_DESC *pix;                       /* this index file */
  813.   {
  814.     int ret;
  815.     ret = find_ix(pe, pix, 0);        /* see if key is already in index */
  816.                                       /* if found, are dupicates are OK? */
  817.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  818.     pe->idxptr = NULLREC;             /* add new key on leaf level */
  819.     return (insert_ix(pe, pix));      /* insert_ix does the work */
  820.   } /* add_key */
  821.  
  822.  
  823. int cdecl locate_key(pe, pix)         /* locate first key */
  824.   ENTRY *pe;                          /* <= this entry */
  825.   IX_DESC *pix;                       /* in this index */
  826.   {
  827.     int ret;
  828.     ret = find_ix(pe, pix, 1);        /* search index for entry */
  829.                                       /* if found, copy it to pe */
  830.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  831.                                       /* else get the next key */
  832.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  833.     return ( ret );
  834.   } /* locate_key */
  835.  
  836.  
  837. int cdecl find_exact(pe, pix)         /* find an exact match */
  838.   ENTRY *pe;                          /* for this entry */
  839.   IX_DESC * pix;                      /* in this index */
  840.   {
  841.     int  ret;
  842.     ENTRY e;
  843.     copy_entry(&e, pe);               /* make a copy of the entry */
  844.     ret = find_key(&e, pix);          /* is it in the index? */
  845.     if ( ret && pci->duplicate)       /* if duplicate key are allowed */
  846.       {                               /* then search for recptr match */
  847.     while (e.recptr != pe->recptr)
  848.     {
  849.       if (next_key(&e, pci) == EOIX) return (0);   /* no more records */
  850.       if (strcmp(e.key, pe->key) != 0) return (0); /* key changed */
  851.     }
  852.       }
  853.     copy_entry(pe, &e);
  854.     return ( ret );
  855.   } /* find_exact */
  856.  
  857.  
  858. /* BPLUS delete key functions */
  859.  
  860. int cdecl delete_key(pe, pix)         /* delete a key */
  861.   ENTRY *pe;                          /* this entry */
  862.   IX_DESC *pix;                       /* in this index */
  863.   {
  864.      ENTRY   e;
  865.      RECPOS  ads;
  866.      int     h, leveli, levelf;
  867.                                       /* search index for exact match */
  868.      if (!find_exact(pe, pix))  return( IX_FAIL );
  869.      h = 1;
  870.      if ((ads = pe->idxptr) != NULLREC)    /* if not the leaf level */
  871.        {
  872.           leveli = pci->level;        /* save current level */
  873.           do                          /* go to leaf level of index */
  874.             {
  875.                retrieve_block(++(pci->level), ads);
  876.                CO(pci->level) = -1;
  877.             }
  878.           while ((ads = block_ptr->p0) != NULLREC);
  879.           CO(pci->level) = 0;
  880.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  881.           levelf = pci->level;        /* save leaf level */
  882.           pci->level = leveli;        /* reset starting level */
  883.           replace_entry(&e);          /* replace with entry from leaf */
  884.           pci->level = levelf;        /* leaf level */
  885.        }
  886.      while ( h )
  887.        {
  888.       /* get block and delete current entry */
  889.           retrieve_block(pci->level, CB(pci->level));
  890.           del_block(block_ptr, CO(pci->level));
  891.           update_block();             /* block has been changed */
  892.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  893.           /* tree was reduced in height */
  894.             {
  895.               if (pci->root.p0 != NULLREC)    /* replace root block */
  896.                 {
  897.                   retrieve_block(++pci->level, pci->root.p0);
  898.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  899.                   (pci->dx.nl)--;           /* decrement number of levels */
  900.                   write_free(block_ptr->brec, block_ptr);  /* reuse space */
  901.                   BUFDIRTY(cache_ptr) = 0;       /* block saved on disk */
  902.                   BUFHANDLE(cache_ptr) = 0;
  903.                 }
  904.               break;
  905.             }
  906.           /* see if we can combine index blocks */
  907.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  908.           if ( h )
  909.               h = combineblk(CB(pci->level), block_ptr->bend);
  910.        }
  911.     find_ix(pe, pix, 0);         /* restore CO and CB for each level */
  912.     return( IX_OK );
  913.   } /* delete_key */
  914.  
  915.  
  916. int pascal combineblk(ads, size)      /* combine index blocks */
  917.   RECPOS ads;                         /* block at this address */
  918.   int size;                           /* and is this size */
  919.   {
  920.     ENTRY  e;
  921.     RECPOS address;
  922.     int    esize, off, ret, saveoff, ibuff;
  923.     ret = 0;
  924.                                    /* ancestor level and save offset */
  925.     saveoff = CO(--(pci->level));
  926.                                    /* retrieve ancestor index block */
  927.     retrieve_block(pci->level, CB(pci->level));
  928.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  929.       /* combine with page on right */
  930.       {
  931.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  932.           /* okay to combine */
  933.           {
  934.             copy_entry(&e, ENT_ADR(block_ptr, off));   /* save entry */
  935.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  936.             retrieve_block(++pci->level, address);
  937.             ibuff = cache_ptr;           /* save cache pointer */
  938.             spare_block = block_ptr;     /* use as spare block */
  939.             retrieve_block(pci->level, ads);
  940.             esize = ENT_SIZE(&e);
  941.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  942.                  && (spare_block->bend <= block_ptr->bend + esize))
  943.                return( ret );
  944.             e.idxptr = spare_block->p0;
  945.             ins_block(block_ptr, &e, block_ptr->bend);
  946.             update_block();
  947.             if ((block_ptr->bend + spare_block->bend) < split_size)
  948.             /* combine the blocks */
  949.               {
  950.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  951.                        ENT_ADR(spare_block, 0),
  952.                        spare_block->bend);
  953.                 /* set block length and free spare block space */
  954.                 block_ptr->bend += spare_block->bend;
  955.                 write_free(spare_block->brec, spare_block);
  956.                 BUFDIRTY(ibuff) = 0;
  957.                 BUFHANDLE(ibuff) = 0;
  958.                 --pci->level;
  959.                 ret = 1;
  960.               }
  961.             else
  962.             /* move an entry up to replace the one moved */
  963.               {
  964.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  965.                 esize = ENT_SIZE(&e);
  966.                 /* fixup spare block and pointers */
  967.                 movedown(spare_block, 0, esize);
  968.                 spare_block->bend -= esize;
  969.                 spare_block->p0 = e.idxptr;
  970.                 BUFDIRTY(ibuff) = 1;
  971.                 --(pci->level);
  972.                 replace_entry(&e);
  973.               }
  974.           }
  975.       }
  976.     else
  977.       /* move from page on left */
  978.       {
  979.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  980.                  < split_size)
  981.           /* okay to proceed */
  982.           {
  983.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));  /* save entry */
  984.             /* get page which is on the left */
  985.             off = prev_entry(saveoff);
  986.             if (CO(pci->level) == -1) address = block_ptr->p0;
  987.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  988.             retrieve_block(++pci->level, address);
  989.             off = last_entry();
  990.             ibuff = cache_ptr;
  991.             /* set spare block to left page */
  992.             spare_block = block_ptr;
  993.             /* get current block */
  994.             retrieve_block(pci->level, ads);
  995.             esize = ENT_SIZE(&e);
  996.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  997.                  && (spare_block->bend <= block_ptr->bend + esize))
  998.                return( ret );
  999.             BUFDIRTY(ibuff) = 1;           /* we have changed things */
  1000.             CO(pci->level) = 0;
  1001.             e.idxptr = block_ptr->p0;
  1002.             ins_block(block_ptr, &e, 0);
  1003.             if ((block_ptr->bend + spare_block->bend) < split_size)
  1004.             /* combine the blocks */
  1005.               {
  1006.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  1007.                        ENT_ADR(block_ptr, 0),
  1008.                        block_ptr->bend);
  1009.                 /* set block length and freeup block */
  1010.                 spare_block->bend += block_ptr->bend;
  1011.                 write_free(block_ptr->brec, block_ptr);
  1012.                 BUFDIRTY(cache_ptr) = 0;
  1013.                 BUFHANDLE(cache_ptr) = 0;
  1014.                 CO(--(pci->level)) = saveoff;
  1015.                 ret = 1;
  1016.               }
  1017.             else
  1018.             /* move an entry up to replace the one moved */
  1019.               {
  1020.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  1021.                  copy_entry(&e, ENT_ADR(spare_block, off));
  1022.                  spare_block->bend = off;
  1023.                  update_block();
  1024.                  CO(--(pci->level)) = saveoff;
  1025.                  replace_entry(&e);
  1026.               }
  1027.           }
  1028.       }
  1029.     return ( ret );
  1030.   } /* combineblk */
  1031.  
  1032.  
  1033. void pascal replace_entry(pe)     /* replace entry at current position */
  1034.   ENTRY *pe;                      /* with this entry */
  1035.   {
  1036.     retrieve_block(pci->level, CB(pci->level));   /* get current block */
  1037.     /* set address for the replacement entry */
  1038.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  1039.     del_block(block_ptr, CO(pci->level));      /* now delete the entry */
  1040.     prev_entry(CO(pci->level));                /* backup one entry */
  1041.     insert_ix(pe, pci);                        /* and insert new entry */
  1042.     update_block();
  1043.   } /* replace_entry */
  1044.  
  1045.